#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//https://blog.csdn.net/weixin_42109012/article/details/92250160
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> myQueue;
        vector<vector<int>> vec;
        cout << "[";
        if (root){
            myQueue.push(root);
            while(!myQueue.empty()){
                TreeNode* node = myQueue.front();
                myQueue.pop();
                cout << node->val << " ";
                if (node->left){
                    myQueue.push(node->left);
                }
                if (node->right){
                    myQueue.push(node->right);
                }
            }
        }
        cout << "]";
        vector<int> vec1;
        vector<int> vec2;
        vector<int> vec3;
        vector<int> vec4;
        vec1.push_back(1);
        vec2.push_back(1);
        vec2.push_back(2);
        vec3.push_back(1);
        vec3.push_back(2);
        vec3.push_back(3);
        vec4.push_back(1);
        vec4.push_back(2);
        vec4.push_back(3);
        vec4.push_back(4);
        vec.push_back(vec1);
        vec.push_back(vec2);
        vec.push_back(vec3);
        vec.push_back(vec4);

        return vec;
    }
};

TreeNode* createTree(int deepth, uint32_t max)
{
    if (deepth <= 0) return NULL;
    int value = rand()%max;
    TreeNode* root = new TreeNode(value);
    TreeNode* ref = root;
    ref->left = createTree(deepth-1, max);
    ref->right = createTree(deepth-1, max);
    return root;
}

void printTree(TreeNode* root)
{
    if (!root) return;
    printf("%d ", root->val);
    printTree(root->left);
    printTree(root->right);
}

void printVector2(vector<vector<int>> &vector2)
{
    vector<vector<int>>::iterator iter;
    for (iter = vector2.begin(); iter != vector2.end(); ++iter){
        for (int i = 0; i < (*iter).size(); ++i){
            cout << (*iter)[i] << " ";
        }
    }
    cout << endl;
}

int main()
{
    Solution su;
    TreeNode* tree;
    srand(clock());
    tree = createTree(5, 20);
    printTree(tree);
    printf("\r\n");
    vector<vector<int>> result = su.levelOrder(tree);
    printVector2(result);
    return 0;
}

